//CSE 430 - Operating Systems
//Partha Dasgupta
//Spring '12
//Project 1

//Alan Tu
//Kelly Jesionowski

#ifndef _Q_H
#define _Q_H

#include <stdio.h>
#include <stdlib.h>

//q-element structure consisting of a prev and next pointer and payload consisting of 1 integer
typedef struct qElem{
	struct qElem* prev;
	struct qElem* next;
	int data;
}qElem_t;


//Forward declarations
qElem_t* NewItem();								//returns a pointer to a new q-element
void InitQueue(qElem_t** head);					//creates an empty queue, pointed to by the variable head
void AddQueue(qElem_t** head, qElem_t* item);	//adds a queue item, pointed to by "item", to the queue pointed to by head
qElem_t* DelQueue(qElem_t** head);				//deletes an item from head and returns a pointer to the deleted item
void RotateQ(qElem_t** head);					//moves the header pointer to the next element in the queue
												//equivalent to AddQueue(&head, DeleteQ(&head)), but simpler and more efficient

//Function defitions
qElem_t* NewItem(){
    qElem_t* item;
    item = (qElem_t*)malloc(sizeof(qElem_t));
    item->next = NULL;
    item->prev = NULL;
    return item;
}

void InitQueue(qElem_t** head){
    *head = NULL;
    return;
}

void AddQueue(qElem_t** head, qElem_t* item){
	if(item->next != NULL || item->prev != NULL){
		printf("Cannot add item already in a queue.\n");
		return;
	}

	if(*head == NULL){
		*head = item;
		(*head)->next = item;
        (*head)->prev = item;
	} else {
		item->next = *head;
		item->prev = (*head)->prev;
		(*head)->prev->next = item;
		(*head)->prev = item;
	}
}

qElem_t* DelQueue(qElem_t** head){
	if(*head == NULL){
		printf("Cannot delete from empty queue.\n");
		return NULL;
	}
	
	qElem_t* deleted;
	
    deleted = *head;
    
	if((*head)->next == *head){
		*head = NULL;
	} else {
		(*head)->prev->next = (*head)->next;	
		(*head)->next->prev = (*head)->prev;
		*head = (*head)->next;
	}
	deleted->next = NULL;
	deleted->prev = NULL;
	return deleted;
}

void RotateQ(qElem_t** head){
	if(*head == NULL){
		printf("Cannot rotate empty queue.\n");
	} else {
        *head = (*head)->next;
	}
}


#endif // _Q_H
